package org.example.day01;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO +
 * 在学校中，N个小朋友站成一队， 第i个小朋友的身高为height[i]，
 * 第i个小朋友可以看到的第一个比自己身高更高的小朋友j，那么j是i的好朋友(要求j > i)。
 * 请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用0代替。
 * 小朋友人数范围是 [0, 40000]。
 * @date 2024/3/11 15:22
 */
public class test003 {
    public static int[] findGoodFriends(int N, int[] height) {
        Stack<Integer> stack = new Stack<>();  // 用于保存小朋友的索引的栈
        int[] result = new int[N];  // 初始化结果数组，初始值为0

        for (int i = 0; i < N; i++) {
            // 当栈不为空且当前小朋友的身高大于栈顶小朋友的身高时，栈顶小朋友是当前小朋友的好朋友
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int j = stack.pop();  // 弹出栈顶元素
                result[j] = i;  // 将栈顶小朋友的好朋友位置设为当前小朋友的索引
            }

            stack.push(i);  // 将当前小朋友的索引入栈
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();  // 输入N
        int[] height = new int[N];  // 初始化身高数组

        for (int i = 0; i < N; i++) {
            height[i] = scanner.nextInt();  // 输入每个小朋友的身高
        }

        int[] result = findGoodFriends(N, height);  // 调用函数找到好朋友的位置

        for (int i = 0; i < N; i++) {
            System.out.print(result[i] + " ");  // 输出结果
        }
    }
}
